Given an edge-weighted directed graph $G=(V,E)$ on $n$ vertices and a set$T=\{t_1, t_2, \ldots, t_p\}$ of $p$ terminals, the objective of the \scss($p$-SCSS) problem is to find an edge set $H\subseteq E$ of minimum weight suchthat $G[H]$ contains an $t_{i}\rightarrow t_j$ path for each $1\leq i\neq j\leqp$. In this paper, we investigate the computational complexity of a variant of$2$-SCSS where we have demands for the number of paths between each terminalpair. Formally, the \sharinggeneral problem is defined as follows: given anedge-weighted directed graph $G=(V,E)$ with weight function $\omega:E\rightarrow \mathbb{R}^{\geq 0}$, two terminal vertices $s, t$, and integers$k_1, k_2$ ; the objective is to find a set of $k_1$ paths $F_1, F_2, \ldots,F_{k_1}$ from $s\leadsto t$ and $k_2$ paths $B_1, B_2, \ldots, B_{k_2}$ from$t\leadsto s$ such that $\sum_{e\in E} \omega(e)\cdot \phi(e)$ is minimized,where $\phi(e)= \max \Big\{|\{i\in [k_1] : e\in F_i\}|\ ,\ |\{j\in [k_2] : e\inB_j\}|\Big\}$. For each $k\geq 1$, we show the following: The \sharing problemcan be solved in $n^{O(k)}$ time. A matching lower bound for our algorithm: the\sharing problem does not have an $f(k)\cdot n^{o(k)}$ algorithm for anycomputable function $f$, unless the Exponential Time Hypothesis (ETH) fails. Our algorithm for \sharing relies on a structural result regarding an optimalsolution followed by using the idea of a "token game" similar to that ofFeldman and Ruhl. We show with an example that the structural result does nothold for the \sharinggeneral problem if $\min\{k_1, k_2\}\geq 2$. Therefore\sharing is the most general problem one can attempt to solve with ourtechniques.
展开▼
机译：给定在$ n $个顶点上的边缘加权有向图$ G =（V，E）$和$ p $终端的集合$ T = \ {t_1，t_2，\ ldots，t_p \} $，目标是\ scss（$ p $ -SCSS）问题是找到最小权重的边集$ H \ subseteq E $，使得每个$ 1 \ leq i的$ G [H] $包含$ t_ {i} \ rightarrow t_j $路径\ neq j \ leqp $。在本文中，我们研究了$ 2 $ -SCSS变体的计算复杂性，其中我们需要每个终端对之间的路径数。形式上，\ sharinggeneral问题的定义如下：给定具有权重函数$ \ omega：E \ rightarrow \ mathbb {R} ^ {\ geq 0} $的边际加权有向图$ G =（V，E）$，两个终端顶点$ s，t $和整数$ k_1，k_2 $;目的是从$ s \ leadsto t $和$ k_2 $路径$ B_1，B_2，\ ldots，B_ {k_2} $找到一组$ k_1 $路径$ F_1，F_2，\ ldots，F_ {k_1} $ from $ t \ leadsto s $，使得$ \ sum_ {e \ in E} \ omega（e）\ cdot \ phi（e）$最小，其中$ \ phi（e）= \ max \ Big \ {| \ {i \ in [k_1]：e \ in F_i \} | \\，\ | \ {j \ in [k_2]：e \ inB_j \} | \\ Big \} $。对于每个$ k \ geq 1 $，我们显示以下内容：\ sharing问题可以在$ n ^ {O（k）} $时间内解决。我们的算法的匹配下限：共享问题没有任何可计算函数$ f $的$ f（k）\ cdot n ^ {o（k）} $算法，除非指数时间假说（ETH）失败。我们的\共享算法基于关于最佳解决方案的结构结果，然后使用类似于费德曼和鲁尔的“代币游戏”的思想。我们以一个示例显示，如果$ \ min \ {k_1，k_2 \} \ geq 2 $，则\ sharinggeneral问题的结构结果不成立。因此，\共享是我们可以尝试解决的最普遍的问题。
展开▼
